package com.java.container;



import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: java_basic_knowledge
 * @description:
 * @author: CaoYong
 * @create: 2021-04-20 09:33
 **/
public class PriorityQueueKnowledge {

    public static  class HowToDefinePriorityQueue<E> {

        private static final int DEFAULT_INITIAL_CAPACITY = 11;
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

        private Object[] queue;
        private int size = 0;
        private Comparator<? super E> comparator;
        private int modCount;

        public HowToDefinePriorityQueue() {
            this(DEFAULT_INITIAL_CAPACITY, null);
        }

        public HowToDefinePriorityQueue(int initialCapacity) {
            this(initialCapacity, null);
        }

        public HowToDefinePriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
            this.queue = new Object[initialCapacity];
            this.comparator = comparator;
        }

        // 入队
        public boolean offer(E e) {
            if (e == null) {
                throw new NullPointerException();
            }
            modCount ++;
            int i = size;
            if (i >= queue.length) {
                grow(i +1);
            }
            size += 1;
            if(i == 0) {
                queue[0] = e;
            }
            else {
                shiftUp(i, e);
            }
            return true;
        }

        private void shiftUp(int k, E x) {
            if (comparator != null) {
                shiftUpUsingComparator(k, x);
            }
            else {
                shiftUpComparable(k, x);
            }
        }

        // 元素上移
        private void shiftUpComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>) x;
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                if (key.compareTo((E) e) >= 0) { // 如果当前节点大于父节点则不改变位置，停止遍历，否则交换当前节点和父节点的位置
                    break;
                }
                queue[k] = e;
                k = parent;
            }
            queue[k] = key;
        }

        private void shiftUpUsingComparator(int k, E x) {
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Object e = queue[parent];
                if (comparator.compare(x, (E)e) >= 0) {
                    break;
                }
                queue[k] = e;
                k = parent;
            }
            queue[k] = x;
        }

        // 数组扩容，如果oldCapacity < 64就扩大一倍，否则扩大50%
        private void grow(int minCapacity) {
            int oldCapacity = queue.length;
            int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                newCapacity = hugeCapacity(minCapacity);
                queue = Arrays.copyOf(queue, newCapacity);
            }
        }

        private int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) {
                throw new OutOfMemoryError();
            }
            return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
        }

        // 查看头部元素
        public E peek() {
            if (size == 0) {
                return null;
            }
            return (E)queue[0];
        }

        public E poll() {
            if (size == 0) {
                return null;
            }
            int s = --size;
            modCount++;
            E result = (E) queue[0];
            E x = (E) queue[s];
            queue[s] = null;
            if (s != 0) {
                shiftDown(0, x);
            }
            return result;
        }

        // 元素下移,根据comparator是否为空选择不同的方法
        private void shiftDown(int k, E x) {
            if(comparator != null) {
                shiftDownUsingComparator(k, x);
            }
            else {
                shitDownComparable(k, x);
            }
        }


        private void shitDownComparable(int k, E x) {
            Comparable<? super E> key = (Comparable<? super E>) x;
            int half = size >>> 1;
            while(k < half) { // k < half及从最后一层非叶子节点开始遍历
                int child = (k << 1) + 1;
                Object c = queue[child];
                int right = child + 1;
                if(right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) { // 获取父节点的两个叶子节点中的最小值
                    c = queue[child = right];
                }
                if (key.compareTo((E) c) <= 0) { //如果父节点小于子节点的的最小值则不改变位置并停止遍历，否则交换父节点和子节点的位置
                    break;
                }
                queue[k] = c;
                k = child;
            }
            queue[k] = key;
        }

        private void shiftDownUsingComparator(int k, E x) {
            int half = size >>> 1;
            while (k < half) {
                int child = (k << 1) + 1;
                Object c = queue[child];
                int right = child + 1;
                if (right < size &&
                        comparator.compare((E) c, (E) queue[right]) > 0) {
                    c = queue[child = right];
                }
                if (comparator.compare(x, (E) c) <= 0) {
                    break;
                }
                queue[k] = c;
                k = child;
            }
            queue[k] = x;
        }
    }


    public static void howToUsePriorityQueue() {
        HowToDefinePriorityQueue tasks = new HowToDefinePriorityQueue(11,  Task.taskComparator);
        tasks.offer(new Task(20, "写日记"));
        tasks.offer(new Task(10, "看电视"));
        tasks.offer(new Task(100, "写代码"));

        Task task = (Task)tasks.poll();
        while (task != null) {
            System.out.println(task);
            task = (Task)tasks.poll();
        }

    }

    public static void main(String[] args) {
        howToUsePriorityQueue();
    }


    static class Task {
        int priority;
        String name;

        public Task(int priority, String name) {
            this.priority = priority;
            this.name = name;
        }

        public int getPriority() {
            return priority;
        }

        public void setPriority(int priority) {
            this.priority = priority;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "Task{" +
                    "priority=" + priority +
                    ", name='" + name + '\'' +
                    '}';
        }

        static Comparator<Task> taskComparator = new Comparator<Task>() {
            @Override
            public int compare(Task o1, Task o2) {
                if(o1.getPriority() > o2.getPriority()) {
                    return -1;
                } else if(o1.getPriority() < o2.getPriority()) {
                    return 1;
                }
                return 0;
            }
        };
    }



}
